๋ฌธ์
Programmers - ๋ธ๋ก ์ด๋ํ๊ธฐ
๐ Logic
private void moveRobot() {
...
}
-
BFS ๋ฐฉ์์ผ๋ก
boardํ์ํ๋ ํจ์๋ก, ์ด 3๋ฒ์for๋ฌธ์ด ์กด์ฌํ๋ค.- ์ฒซ๋ฒ์งธ๋ ์ฃผ์ด์ง ์ขํ๋ก๋ถํฐ ์ด๋ ๊ฐ๋ฅํ ์ํ์ข์ฐ ์ขํ๋ฅผ queue์ ์ถ๊ฐ
- ๋๋ฒ์งธ์ ์ธ๋ฒ์ฌ๋ ๋ก๋ด์ ์ขํ ์ค ํ๋๋ฅผ ๊ธฐ์ค์ผ๋ก 90๋ ํ์ ํ์ฌ ๊ฐ ์ ์๋ ์ขํ๋ฅผ queue์ ์ถ๊ฐ
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.util.*;
class Robot {
int x1;
int y1;
int dir;
int cost;
public Robot(int x1, int y1, int dir, int cost) {
this.x1 = x1;
this.y1 = y1;
this.dir = dir;
this.cost = cost;
}
}
class Solution {
static int[][] board;
static int size;
static int answer = 0;
public int solution(int[][] board) {
this.board = board;
this.size = board.length;
moveRobot();
return answer;
}
private void moveRobot() {
int[] xRange = {0, 1, 0, -1};
int[] yRange = {1, 0, -1, 0};
// ํ์ ์์ ์ฌ์ฉํ ๋ฒ์ ๋ฐฐ์ด
int[] rxRange = {-1, 1, 1, -1};
int[] ryRange = {1, 1, -1, -1};
boolean[][][] visited = new boolean[size][size][4];
// Queue์๋ ์ผ์ชฝ ์ขํ๋ง ์ถ๊ฐ
Queue<Robot> queue = new LinkedList<>();
int x1, y1, x2, y2, dir, cost;
int nx1, ny1, nx2, ny2, ndir;
queue.add(new Robot(0, 0, 0, 0));
visited[0][0][0] = true;
while (!queue.isEmpty()) {
Robot robot = queue.poll();
x1 = robot.x1;
y1 = robot.y1;
dir = robot.dir;
cost = robot.cost;
x2 = x1 + xRange[dir];
y2 = y1 + yRange[dir];
// ์ข
๋ฃ
if (isFinish(x1, y1) || isFinish(x2, y2)) {
answer = cost;
return;
}
// ์ํ์ข์ฐ๋ก ๋ก๋ด ์ด๋
for (int r = 0; r < 4; r++) {
nx1 = x1 + xRange[r];
ny1 = y1 + yRange[r];
nx2 = x2 + xRange[r];
ny2 = y2 + yRange[r];
if (!checkBoundary(nx1, ny1) || !checkBoundary(nx2, ny2)) continue;
if (board[nx1][ny1] == 1 || board[nx2][ny2] == 1) continue;
if (visited[nx1][ny1][dir]) continue;
visited[nx1][ny1][dir] = true;
queue.add(new Robot(nx1, ny1, dir, cost + 1));
}
int rx, ry, tempDir;
// x1, y1๋ฅผ ๊ธฐ์ค์ผ๋ก 90๋ ํ์
// ndir์ 0(์ค๋ฅธ์ชฝ ๋๊ฐ์ ์), 1(์ค๋ฅธ์ชฝ ๋๊ฐ์ ์๋), 2(์ผ์ชฝ ๋๊ฐ์ ์๋), 3(์ผ์ชฝ ๋๊ฐ์ ์) ์ค ํ๋
for (int i = 1; i < 4; i += 2) {
ndir = computeDir(dir, i);
nx2 = x1 + xRange[ndir];
ny2 = y1 + yRange[ndir];
tempDir = (i == 1) ? ndir : dir;
rx = x1 + rxRange[tempDir];
ry = y1 + ryRange[tempDir];
if (!checkBoundary(nx2, ny2) || !checkBoundary(rx, ry)) continue;
if (board[nx2][ny2] == 1 || board[rx][ry] == 1) continue;
if (visited[x1][y1][ndir]) continue;
visited[x1][y1][ndir] = true;
queue.add(new Robot(x1, y1, ndir, cost + 1));
}
// ๋ฐ๋ ๋ฐฉํฅ ์ฒ๋ฆฌ
// x2, y2๋ฅผ ๊ธฐ์ค์ผ๋ก 90๋ ํ์
dir = computeDir(dir, 2);
for (int i = 1; i < 4; i += 2) {
ndir = computeDir(dir, i);
nx1 = x2 + xRange[ndir];
ny1 = y2 + yRange[ndir];
tempDir = (i == 1) ? ndir : dir;
rx = x2 + rxRange[tempDir];
ry = y2 + ryRange[tempDir];
ndir = (ndir + 2) % 4;
if (!checkBoundary(nx1, ny1) || !checkBoundary(rx, ry)) continue;
if (board[nx1][ny1] == 1 || board[rx][ry] == 1) continue;
if (visited[nx1][ny1][ndir]) continue;
visited[nx1][ny1][ndir] = true;
queue.add(new Robot(nx1, ny1, ndir, cost + 1));
}
}
}
private boolean checkBoundary(int x, int y) {
return x >= 0 && x < size && y >= 0 && y < size;
}
private boolean isFinish(int x, int y) {
return x == size - 1 && y == size - 1;
}
private int computeDir(int dir, int i) {
return (dir + i) % 4;
}
}
โ๏ธ Review
- BFS๋ฅผ ์ฌ์ฉํด ๋ชฉ์ ์ง๊น์ง ์ต์ ๋น์ฉ์ ๊ตฌํ๋ ๋ฌธ์ ๋ผ ํ๋จํ๋ค. ๊ทธ๋ํ ํ์ ์์๋ DFS, BFS๊ฐ ๊ฐ๋ฅํ๋ฐ, BFS๊ฐ ์ต์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋๋ฐ ๋ ํจ์จ์ ์ธ ์๊ณ ๋ฆฌ์ฆ์ด๋ผ๋ ๊ฒ์ ๋ฐฐ์ ๋ ๊ธฐ์ต์ด ๋ BFS๋ฅผ ์ฌ์ฉํ๋ค.
- ์์ด๋์ด ์์ฒด๋ ์ฝ๊ฒ ๋ ์ฌ๋ ธ๋ค๋ง, ๋ก๋ด์ ์ขํ๊ฐ 2๊ฐ์ธ ์ ๊ณผ ์ด์ ๋ํ ํ์ ๊ตฌํ์ ์์ด ์ด๋ ค์ ๋ค ..